//
//  128. 最长连续序列.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/8/29.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation

class Solution128 {
    // 最长连续子序列
    // 这个题很有意思：
    func longestConsecutive(_ nums: [Int]) -> Int {
        var dp: [Int: Int] = [:]
        var maxLength = 0
        for i in 0..<nums.count {
            // 如果不在hash表里
            if let _ = dp[nums[i]] {
                continue
            }
            // 在hash表里,看其左边的长度
            // 在hash表里，看其右边的长度
            let left = dp[nums[i] - 1] ?? 0
            let right = dp[nums[i] + 1] ?? 0
            // 真正的长度
            let value = left + right + 1
            // 更新"最左边"的长度,即可
            // 更新"最右边"的长度，即可
            // 更新自己的长度
            dp[nums[i] - left] = value
            dp[nums[i] + right] = value
            dp[nums[i]] = value
            maxLength = max(maxLength, value)
        }
        return maxLength
    }
   static func test() {
        let solution = Solution128()
        let nums =  [4,0,-4,-2,2,5,2,0,-8,-8,-8,-8,-1,7,4,5,5,-4,6,6,-3]
        let result = solution.longestConsecutive(nums)
        print(result)
    }

}
